/*
	Trivial application that displays a string - 4/96 PNL
*/

public class TrivialApplication {

	public static void main(String args[]) {
		Stopwatch watch = new Stopwatch();
		watch.reset().start();
		Towers(25,'A','B','C');
		watch.stop();
	
		System.out.println("Time to solve recursively = "+
			watch.getElapsedTime());
		watch.reset().start();
		LinearTowers(25,'A','B','C');
		watch.stop();
		System.out.println("Time to solve lineraly = "+
			watch.getElapsedTime());
	}
	
	public static void Towers(int numDisks, char src, char dest, char temp){
		if (numDisks == 1){
			System.out.println("Move top disk from pole "+
					src+" to pole "+dest);
		} else {
			Towers(numDisks-1,src,temp,dest);
			Towers(1,src,dest,temp);
			Towers(numDisks-1,temp,dest,src);
		}			
	}	
	
	public static void LinearTowers(int orig_numDisks, char orig_src, 
			char orig_dest, char orig_temp){
		int numDisksStack[] =  new int[100];
		char srcStack[] = new char[100];
		char destStack[] = new char[100];
		char tempStack[] = new char[100];
		int stacktop = 0;
		
		numDisksStack[0] = orig_numDisks;
		srcStack[0] = orig_src;
		destStack[0] = orig_dest;
		tempStack[0] = orig_temp;
		stacktop++;
		while (stacktop>0) { // this is the same as having call frames on teh system stack
			stacktop--; // pop current off stack
			int numDisks = numDisksStack[stacktop];
			char src = srcStack[stacktop];
			char dest = destStack[stacktop];
			char temp = tempStack[stacktop];
			if (numDisks == 1) {
					System.out.println("Move top disk from pole "+
							src+" to pole "+dest);					
			} else {
			    /* do this after the other two */
				/* Towers(numDisks-1,temp,dest,src); */
				numDisksStack[stacktop] = numDisks -1;
				srcStack[stacktop] = temp;
				destStack[stacktop] = dest;
				tempStack[stacktop++] = src;
				/* do this after the first */
				/* Towers(1,src,dest,temp); */
				numDisksStack[stacktop] =1;
				srcStack[stacktop] = src;
				destStack[stacktop] = dest;
				tempStack[stacktop++] = temp;
				/* do this first */
				/* Towers(numDisks-1,src,temp,dest); */
				numDisksStack[stacktop] = numDisks -1;
				srcStack[stacktop] = src;
				destStack[stacktop] = temp;
				tempStack[stacktop++] = dest;								
			}	

		}
	}	
}
